package J20250227_dfs;

/**
 * Created with IntelliJ IDEA.
 * Description: 递归5——8
 * User: 王圆豪
 * Date: 2025-03-01
 * Time: 19:57
 */

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
}

public class Solution2 {
    //Pow（x,n）-快速幂——https://leetcode.cn/problems/powx-n/
    public double myPow(double x, int n) {
        return n > 0 ? dfs(x,n) : 1.0/dfs(x,-n);
    }

    public double dfs(double x, int n){
        if(n == 0) return 1.0;
        double tmp = dfs(x,n/2);
        return n % 2 == 0 ? tmp * tmp : x * tmp * tmp;
    }

    //计算布尔⼆叉树的值——https://leetcode.cn/problems/evaluate-boolean-binary-tree/
    public boolean evaluateTree(TreeNode root) {
        return dfs1(root);
    }

    public boolean dfs1(TreeNode root){
        if(root.val == 1 || root.val == 0) return root.val == 0 ? false : true;
        boolean a = dfs1(root.left);
        boolean b = dfs1(root.right);
        return root.val == 2 ? a || b : a && b;
    }

    //求根节点到叶节点数字之和——https://leetcode.cn/problems/sum-root-to-leaf-numbers/
    public int sumNumbers(TreeNode root) {
        return dfs(root, 0);
    }

    public int dfs(TreeNode root, int v){
        int a = v*10 + root.val;
        if(root.left == null && root.right == null) return a;
        int ret = 0;
        if(root.left != null){
            ret += dfs(root.left, a);
        }
        if(root.right != null){
            ret += dfs(root.right, a);
        }
        return ret;
    }

    //⼆叉树剪枝——https://leetcode.cn/problems/binary-tree-pruning/
    public TreeNode pruneTree(TreeNode root) {
        return dfs2(root);
    }

    public TreeNode dfs2(TreeNode root){
        if(root == null) return null;
        root.left = dfs2(root.left);
        root.right = dfs2(root.right);
        return (root.left == null && root.right == null && root.val == 0) ? null : root;
    }

}
